Richard's Last Problem

Nicholas Wheeler
3 February 2013

Problem posed

On the evening of 16 May 2012, Richard Crandall (from his iPhone, inevitably) sent me the note reproduced below:

Nicholas,

I have a fascinating engineering problem that comes down to the following question: Let

𝕌=(({{a, b}, {c, d}}))

be unimodular (Det[𝕌] = 1). Is there an elegant way to factor 𝕌 into

𝕌=ℝ𝕊

where ℝ is a rotation matrix

ℝ=(({{Cos[t], -Sin[t]}, {Sin[t], Cos[t]}}))

and 𝕊 has "simple" structure? I suppose I am asking for a way to factor 𝕌 such that 𝕊 has only a few (less than 4) parameters?

r

On 18 May I sent Richard email to which was attached the following Mathematica notebook (v7):

Richard's Problem

Nicholas Wheeler
18 May 2012

Introduction

Let

𝕌=(({{a, b}, {c, d}}));

be unimodular. Richard asks (16 May 2012) "Is there an elegant way to write 𝕌 in factored form 𝕌 = ℝ𝕊 where ℝ is a rotation matrix and 𝕊 is as simple as possible?"

General properties of 2 × 2 unimodular matrices

Unprotect[D];

Introduce the notations

T=Tr[𝕌];
D=Det[𝕌];

The characteristic polynomial of 𝕌 becomes

CharacteristicPolynomial[𝕌,x]==(x^2)-T x+D//Simplify

and when we assume unimodularity becomes

p[x_]:=(x^2)-T x+1

From

Clear[T]
Solve[p[x]==0,x]//Simplify

we obtain eigenvalues

(Subscript[λ, 1])=(1/2) (T+(Sqrt[-4+(T^2)]));
(Subscript[λ, 2])=(1/2) (T-(Sqrt[-4+(T^2)]));

Simplify[(Subscript[λ, 1])+(Subscript[λ, 2])]
Simplify[(Subscript[λ, 1])(Subscript[λ, 2])]

Evidently, unimodular 2 × 2 matrices with identical traces have identical spectra. 

Assuming the elements of 𝕌 to be real, the eigenvalues are real iff (T^2)⩾4 and the spectrum becomes degenerate when (T^2)=4.

Solution

Occupying a special place within the population of matrices with specified trace  t are those of the manifestly unimodular form

𝕊=(({{t, s}, {-1/s, 0}}));

Let

ℝ=(({{Cos[β], -Sin[β]}, {Sin[β], Cos[β]}}));

Then

ℝ.𝕊//MatrixForm

Such 3-parameter matrices are trivially unimodular:

Simplify[Det[ℝ.𝕊]]

To cast

𝕌//MatrixForm

into that form we set

Tan[β]=d/b

s=(Sqrt[(b^2)+(d^2)])

t=(a-(d/((b^2)+(d^2))))s/b

The first pair of those equations admit of trivial geometrical representation. The first permits the ℝ matrix to be written

𝕣=(1/(Sqrt[(b^2)+(d^2)]))(({{b, -d}, {d, b}}));

which is indeed rotational:

Simplify[𝕣.Transpose[𝕣]]//MatrixForm

The product ℝ𝕊 has become

𝕣.(({{(a-(d/((b^2)+(d^2))))(Sqrt[(b^2)+(d^2)])/b, (Sqrt[(b^2)+(d^2)])}, {((-1)/(Sqrt[(b^2)+(d^2)])), 0}}))//Simplify

which is seen to be a manifestly unimodular rendition of 𝕌.

Spectral decomposition

Though the solution of the problem that motivated this exercise is now in hand, I carry the discussion forward a little way to see whether things stay simple or get uninformatively complicated, and to establish one small but curious point.

Clear[𝕊,t,s]
𝕊=(({{t, s}, {-1/s, 0}}));

From

Eigenvalues[𝕊]

(Subscript[λ, 1])=(1/2) (t+(Sqrt[-4+(t^2)]));
(Subscript[λ, 2])=(1/2) (t-(Sqrt[-4+(t^2)]));

we see that the (right) eigenvectors

Eigenvectors[𝕊]

are quite simple:

(Subscript[r, 1])=(({{-s (Subscript[λ, 1])}, {1}}));
(Subscript[r, 2])=(({{-s (Subscript[λ, 2])}, {1}}));

Simplify[𝕊.(Subscript[r, 1])==(Subscript[λ, 1])(Subscript[r, 1])]
Simplify[𝕊.(Subscript[r, 2])==(Subscript[λ, 2])(Subscript[r, 2])]

Transposition of 𝕊 is accomplished by the simple replacement

so the left eigenvectors of 𝕊 (transposed right eigenvectors of 𝕊 transpose) are

(Subscript[l, 1])=(({{(Subscript[λ, 1])/s, 1}}));
(Subscript[l, 2])=(({{(Subscript[λ, 2])/s, 1}}));

Simplify[(Subscript[l, 1]).𝕊==(Subscript[λ, 1])(Subscript[l, 1])]
Simplify[(Subscript[l, 2]).𝕊==(Subscript[λ, 2])(Subscript[l, 2])]

Introducing the inner product function

f[x_,y_]:=Simplify[x.y][[1]][[1]]

we have these biorthogonality relations:

f[(Subscript[l, 1]),(Subscript[r, 2])]
f[(Subscript[l, 2]),(Subscript[r, 1])]

while

f[(Subscript[l, 1]),(Subscript[r, 1])]==1-((Subscript[λ, 1])^2)//Simplify
f[(Subscript[l, 2]),(Subscript[r, 2])]==1-((Subscript[λ, 2])^2)//Simplify

Proceeding now along lines spelled out on page 5 of "Some uncommon matrix theory" (April 2012), we construct

(Subscript[r, 1]).(Subscript[l, 1])//MatrixForm

%==(({{-((Subscript[λ, 1])^2), -s (Subscript[λ, 1])}, {(Subscript[λ, 1])/s, 1}}))

(Subscript[r, 2]).(Subscript[l, 2])//MatrixForm

%==(({{-((Subscript[λ, 2])^2), -s (Subscript[λ, 2])}, {(Subscript[λ, 2])/s, 1}}))

and on the basis of that information define

(Subscript[ℙ, 1])=(1/(1-((Subscript[λ, 1])^2)))(({{-((Subscript[λ, 1])^2), -s (Subscript[λ, 1])}, {(Subscript[λ, 1])/s, 1}}));
(Subscript[ℙ, 2])=(1/(1-((Subscript[λ, 2])^2)))(({{-((Subscript[λ, 2])^2), -s (Subscript[λ, 2])}, {(Subscript[λ, 2])/s, 1}}));

which we verify comprise a COMPLETE

(Subscript[ℙ, 1])+(Subscript[ℙ, 2])//Simplify//MatrixForm

set of ORTHOGONAL

(Subscript[ℙ, 1]).(Subscript[ℙ, 2])//Simplify//MatrixForm

PROJECTION MATRICES:

(Subscript[ℙ, 1]).(Subscript[ℙ, 1])-(Subscript[ℙ, 1 ])//Simplify//MatrixForm
(Subscript[ℙ, 2]).(Subscript[ℙ, 2])-(Subscript[ℙ, 2 ])//Simplify//MatrixForm

We have now in hand the ("generalized") spectral decomposition of 𝕊:

(Subscript[λ, 1])(Subscript[ℙ, 1])+(Subscript[λ, 2])(Subscript[ℙ, 2])==𝕊//Simplify//MatrixForm

We are in position to describe  (Subscript[λ, 1]),(Subscript[λ, 2]) and the elements of (Subscript[ℙ, 1]),(Subscript[ℙ, 2]) and 𝕊 in terms of the elements  a, b, d  of  𝕌, and to write

but this is NOT the spectral decomposition of 𝕌: we established early on that the eigenvalues of 𝕌

Eigenvalues[{{a,b},{((-1+a d)/b),d}}]

Assuming[a+d==T,Simplify[%]]

possess the form of the eigenvalues of 𝕊

but they differ in value, because

Moreover, the matrices

do not comprise a complete set of orthogonal projection operators. They would if the transformation

were a rotational similarity transformation, but it isn't  (is lop-sided). To construct the spectral decomposition of 𝕌 one would have to work from

Eigenvectors[{{a,b},{((-1+a d)/b),d}}]

Assuming[a+d==T,Simplify[%]]

which I will not take the trouble to do; I don't off-hand see the utility of such a result, and anyway I have already established the point I wanted to make…which is that the lop-sided nature of Richard's transformation tends to throw things out of kilter.

Richard's response, and follow-up problem

On the evening (again at 7:26 PM; seems to have been his habit to write during dinner) of 18 June 2012 Richard responded:

Nicholas,

I am delighted to say, your latest unimodular matrix analysis has aided me a great deal in the analysis of stereo audio signals. I owe you a big favor for that!

So my next dilemma, if it interests you, is this:

Being as a unimodular matrix

𝕌=(({{a, b}, {c, d}}))

has Det[𝕌]=1, which is one constraint, we expect the whole unimodular set has 3 genuine parameters.

So you have shown me one such 3-parameter composition in your previous analysis…so far so good.

Now, in the world of digital stereo sound, we are interested in so-called "lifting" matrices of the form

both of which have Det 1.

My new question for your expertise is: Can any unimodular matrix be expresed as a product of three such lifting marices?

I am not changing the original question—in fact, I'm already using what you sent me, to good effect! There are engineering efficiencies to be gained, though, by this new question/foray!

r

PS Sir Michael Berry gave me a gift for you. I have it in my possession, and shall deliver same to you when mutually convenient. [The gift was a thumbdrive containing Berry's collected works.]

[Concerning the reference to Berry (to whom Richard invariably referred in recent years as "Sir Michael":  how much pleasure it would have given Richard to have become "Sir Richard"! Which, had he lived on the other side of the Atlantic, I think he might well have managed to do.): Berry had a speaking engagement in Portland in late May. Richard had arranged lunch with Berry, and had invited me to tag along, since he knew I shared his admiration of Berry's work. On 27 May he wrote

Nicholas,

I am hiring my company chauffeur to drive me to the Michael Berry luncheon on 31 May. You are welcome to ride with us, to avoid downtown parking completely. If you wish, we can pick you up at 12:30 in the Reed parking lot, and after lunch we would deliver you back to Reed. Tell me your preference! 

I had, however, a conflicting obligation, and had to miss the lunch. 

In correspondence with Berry after Richard's death I reminded him that he and I had met (glancingly) when he visited Reed maybe twenty years previously, on which occasion Richard had arranged an on-campus post-seminar departmental dinner with Berry and his beautiful companion. Berry responded that he had recollection neither of me nor of Richard, but did have vivid recollection of a conversation with David Griffiths! He referred to Richard as a person whom—to his regret—he had met only recently (in Portland, and again at the Simon Fraser conference), and whose last words to him had been "We must do a paper together."]

Oya and I were in California during the final ten days of June (home-exchange in Davis, visited David Griffiths at his Inverness retreat), so it was 2 July before I could respond:

Richard's 2nd Problem

Nicholas Wheeler
2 July 2012

Introduction

The following matrices

ℙ=(({{1, a}, {0, 1}})).(({{1, 0}, {b, 1}})).(({{1, c}, {0, 1}}));
ℚ=(({{1, 0}, {b, 1}})).(({{1, c}, {0, 1}})).(({{1, 0}, {d, 1}}));

are, for all real/complex values of {a, b, c, d}, manifestly unimodular. When spelled out in detail, they read

ℙ//MatrixForm
ℚ//MatrixForm

On 18 June, Richard posed this question: Can every 2 × 2 unimodular matrix be presented in factored form as an instance of a ℙ-matrix? a ℚ-matrix?

Numerical evidence that the answer is YES

Construct at random a 2 × 2 real unimodular matrix

𝕦=RandomReal[{},{2,2}];
𝕌=(1/(Sqrt[Det[𝕦]]))𝕦;
𝕌//MatrixForm
Det[𝕌]

Give names to its elements

w=𝕌[[1]][[1]];
x=𝕌[[1]][[2]];
y=𝕌[[2]][[1]];
z=𝕌[[2]][[2]];

(({{w, x}, {y, z}}))==𝕌

and to construct the ℙ-representation of 𝕌 proceed

Solve[{w==1+a b,y==b,z==1+b c},{a,b,c}]

Those results could have been obtained by simple algebra

a=((w-1)/y)
b=y
c=((z-1)/y)

and, by way of verification, supply

x==a+(1+a b)c

Clear[a,b,c,d]

To construct the ℚ-representation of 𝕌 we proceed

Solve[{w==1+c d,x==c,z==1+b c},{b,c,d}]

which by simple algebra could have been obtained from

b=((z-1)/x)
c=x
d=((w-1)/x)

and, by way of verification, supply

y==b+(1+b c)d

Generalization to complex unimodulars

All of which works out perfectly well when 𝕌 is complex:

𝕦=RandomComplex[{},{2,2}];
𝕌=(1/(Sqrt[Det[𝕦]]))𝕦;
𝕌//MatrixForm
Det[𝕌]//Chop

I do not explore the details because I assume Richard's 𝕌-matrices to be real.

Application to matrices of Richard's 1st canonical form

Clear[w,x,y,z,a,b,c,d]

In a previous notebook we have established that every real 2 × 2 unimodular can be presented

in "canonical form" with

w=t Cos[β]+((Sin[β])/s);
x=s Cos[β];
y=-((Cos[β])/s)+t Sin[β];
z=s Sin[β];

To obtain the ℙ-representation of such a matrix we have

a=((w-1)/y)//Simplify
b=y//Simplify
c=((z-1)/y)//Simplify

ℙ//Simplify

Det[%]//Simplify

and could proceed similarly to construct the ℚ-representations of such matrices.

The "factored" and "canonical" presentations of 𝕌 do not appear to stand in an attractively natural relationship.

Richard's final mail

On 24 October 2012 Richard spoke at the Reed Physics Seminar, and took that opportunity to relay to me the Michael Berry gift that had been in his possession since late May (and of which, he told me, he had made a copy).  At dinner—from which,  though held in his honor, he departed early, as was his custom, and which marked the last occasion we were together, the last time I saw him—I asked him "whether anything ever came of that unimodular stuff," but in the noisy confusion of dinner conversation got only a vaguely affirmative word of response.  But at 11:41 that evening he wrote

Nicholas my eternal colleague:

I meant it when I said tonight your unimodular matrix decomposition found its way into Apple technology. 

The basic idea is, treat stereo left/right sound as a column vector (Left, Right) transpose, and "hit it" with a unimodular matrix.  Point being, the resulting entropy (compressibility) is enhanced by this procedure, via compression techniques.

We can talk about this more, but I need to thank you once again!

r

At the time I dismissed his "eternal colleague" as another instance of Richard's occasional tendency toward florid writing, and to the strangely reverent regard which he seems for 45 years to have held for me…which I never understood (attributed to the sentimentality that was a component of his complex personality), certainly did not deserve, and found flatteringly embarrassing. But in retrospect  I have to wonder whether it reflected a premonition that the days in which we would live as colleagues were numbered.

Richard was always quick to respond to problems that I fed his way…of which the most recent (2009?) had to do with statistical properties of the function q[n,m] defined

q[n,m] = # of m-term elements among the partitions of n

But in recent years I gained the feeling that the problems that he in his turn fed to me were—such as the problems treated in this notebook—"baby problems," problems that he thought would lie still within my reach, and from the solution of which I could take an old man's sense that I was still useful. 
 

On the afternoon of 5 November, Richard distributed to members of the physics faculty (+ Tom Wieting and Joe Buhler) the pdf drafts of two papers

"The Poisson equation and 'natural' Madelung constants" (27 October  2012)

"Lattice sums arising from the Poisson equation" (27 October 2012), with co-authors David H. Bailey, Jonathan Borwein & John Zucker

with this text:

Colleagues,

Please find attached two papers on Poisson solutions, as follow-up on my seminar of two weeks ago.

It still astounds me that modern graphics engineering is so well connected with the classical Euler-Lagrange picture, so to speak.

R. E. Crandall

And on 14 November 2012 Richard sent (to Wheeler, Wieting, Powell, Essick, Franklin and Griffiths of the Reed physics/math departments) a note that read

Colleagues,

Pertaining to some research I mentioned recently at a seminar dinner…

Attached is my slideshow from the 2-3 November 2012 SFU Riemann-zeta Conference, where Sir Michael Berry and I and some other colleagues waxed on the Riemann zeta function.

cheers
r

The 18-page slideshow in question was entitled "Analytical algorithms for prime numbers."

That was the last mail I received from Richard; within six weeks (37 days) he was dead.

Though Richard seemed (in all of its complexity) his normal self when we were together on 24 October,  Jonathan Borwein

Hyperlink["Borwein's Obituary","http://experimentalmath.info/blog/2012/12/mathematicianphysicistinventor-richard-crandall-dies-at-64/"]

has remarked that he was "clearly not well" when he spoke on 2 November at the Simon Fraser University Zeta Function Workshop.